#ifndef TACORES_FORDFULKERSON_H
#define TACORES_FORDFULKERSON_H

using namespace std;

#include "FindAugmentingPath.h"
#include "FlowNetwork.h"
#include "VertexInfo.h"
#include <vector>
#include <limits>

class FordFulkerson
{
public:
	FordFulkerson(FlowNetwork network)
		: network(network) {}

	bool compute()
	{
		bool augmented = false;
		for(;;)
		{
			vector<VertexInfo> vertices;
			vertices.resize(numVertices);
			if(!findAugmentingPath.find(vertices))
			{
				break;
			}
			processPath(vertices);
			augmented = true;
		}
		return augmented;
	}

private:
	FlowNetwork& network;
	FindAugmentingPath findAugmentingPath;

	void processPath(vector<VertexInfo>& vertices)
	{
		int v = network.sinkIndex;
		int delta = numeric_limits<int>::max();

		while(v != network.sourceIndex)
		{
			int u = vertices[v].previous;
			int flow;
			if(vertices[v].forward)
			{
				flow = network.edge(u, v).capacity - network.edge(u, v).flow;
			}
			else
			{
				flow = network.edge(v, u).flow;
			}
			if(flow < delta)
			{
				delta = flow;
			}
			v = u;
		}
		v = network.sinkIndex;
		while(v != network.sourceIndex)
		{
			int u = vertices[v].previous;
			if(vertices[v].forward)
			{
				network.edge(u, v).flow += delta;
			}
			else
			{
				network.edge(v, u).flow -= delta;
			}
			v = u;
		}
	}
};

#endif

